﻿#define _CRT_SECURE_NO_WARNINGS


//#include <iostream>
//#include <string>
//
//using namespace std;
//
//const int INF = 32767;
//
//typedef struct
//{
//	string s;
//}Road;
//
//void Disp(int n, int a[][4], Road p[][4]) {
//	for (int i = 0; i < 4; ++i) {
//		if (i == 2) printf("path(%-2d)=|", n);
//		else printf("         |");
//
//		for (int j = 0; j < 4; ++j)
//		{
//			cout.width(4);
//			cout << p[i][j].s << " ";
//		}
//		printf("|\t\t");
//
//		if (i == 2) printf("A(%-2d)=|", n);
//		else printf("      |");
//
//		for (int j = 0; j < 4; ++j)
//		{
//			if (a[i][j] == INF) printf(" ¡Þ ");
//			else printf(" %-2d ", a[i][j]);
//		}
//		printf("|\n");
//	}
//	puts("");
//}
//void Floyd(int a[][4], Road p[][4]) {
//	string t;
//	Disp(-1, a, p);
//
//	for (int k = 0; k < 4; ++k)
//	{
//		for (int i = 0; i < 4; ++i)
//			for (int j = 0; j < 4; ++j)
//			{
//				if (a[i][j] > a[i][k] + a[k][j])
//				{
//					a[i][j] = a[i][k] + a[k][j];
//					if (p[i][k].s[0] == k + '0')
//					{
//						t = p[k][j].s;
//						for (int e = 1; p[i][k].s[e]; ++e)
//							t += p[i][k].s[e];
//						p[i][j].s = t;
//					}
//					else
//					{
//						t = p[i][k].s;
//						for (int e = 1; p[k][j].s[e]; ++e)
//							t += p[k][j].s[e];
//						p[i][j].s = t;
//					}
//				}
//			}
//		Disp(k, a, p);
//	}
//}
//
//void PRoad(int a[][4], Road p[][4])
//{
//	for (int i = 0; i < 4; ++i) {
//		for (int j = 0; j < 4; ++j)
//		{
//			printf("From %d to %d : %d \t %c", i, j, a[i][j], p[i][j].s[0]);
//			for (int k = 1; p[i][j].s[k]; ++k) printf(" -> %c", p[i][j].s[k]);
//			puts("");
//		}
//		puts("");
//	}
//}
//int main()
//{
//	Road path0[4][4] =
//	{
//		{"00", "01", "02", "03"},
//		{"10", "11", "12", "13"},
//		{"20", "21", "22", "23"},
//		{"30", "31", "32", "33"}
//	};
//	int a0[4][4] = {
//					{0, 1, INF, 4},
//					{INF, 0, 9, 2},
//					{3, 5, 0, 8},
//					{INF, INF, 6, 0}
//	};
//	Floyd(a0, path0);
//	PRoad(a0, path0);
//	return 0;
//}





//#include <iostream>
//#include<cstring>
//#define INF 32767
//using namespace std;
//
//const int MAXN = 1e3;
//
//struct {
//	int pre, next, w;
//}path[MAXN] = { {0, 1, 4}, {0, 2, 6}, {0, 3, 6},
//				{1, 2, 1}, {1, 4, 7}, {2, 4, 6},
//				{2, 5, 4}, {3, 2, 2}, {3, 5, 5},
//				{4, 6, 6}, {5, 4, 1}, {5, 6, 8} };
//
//struct {	//邻接矩阵
//	int edges[MAXN][MAXN];
//}G;
//
//void graph_create() {//转化为邻接矩阵
//	for (int i = 0; i < 7; ++i) {
//		for (int j = 0; j < 7; ++j) {
//			if (i == j) G.edges[i][j] = 0;
//			else G.edges[i][j] = INF;
//		}
//	}
//	for (int i = 0; i < 12; ++i) {
//		G.edges[path[i].pre][path[i].next] = path[i].w;
//	}
//}
//
//void Dijkstra(int v) {
//	int dist[MAXN], road[MAXN];
//	bool S[MAXN];
//	bool st[MAXN];
//	for (int i = 0; i < 7; ++i) {
//		S[i] = false;
//		dist[i] = G.edges[v][i];
//		if (dist[i] != INF) road[i] = v;
//		else road[i] = -1;
//	}
//	S[v] = true; road[v] = 0;
//	for (int i = 0; i < 7; ++i) {
//		if (dist[i] == INF) printf(" ∞ ");
//		else printf(" %-2d ", dist[i]);
//	}
//	printf("\t");
//	for (int i = 0; i < 7; ++i) printf(" %-2d ", road[i]);
//	puts("");
//	int min, k;
//	for (int i = 0; i < 6; ++i) {
//		min = INF;
//		for (int j = 0; j < 7; ++j)
//			if (!S[j] && dist[j] < min) {
//				min = dist[j];
//				k = j;
//			}
//		S[k] = true;
//		memset(st, false, sizeof(st));
//		for (int j = 0; j < 7; ++j) {
//			if (!S[j]) {
//				if (dist[j] > dist[k] + G.edges[k][j]) {
//					dist[j] = dist[k] + G.edges[k][j];
//					road[j] = k;
//					printf("(%-2d)", dist[j]);
//					st[j] = true;
//				}
//				else if (dist[j] != INF) printf(" %-2d ", dist[j]);
//				else printf(" ∞ ");
//			}
//			else printf(" %-2d ", dist[j]);
//		}
//		printf("\t");
//		for (int j = 0; j < 7; ++j) {
//			if (!st[j]) printf(" %-2d ", road[j]);
//			else printf("(%-2d)", road[j]);
//		}
//		puts("");
//	}
//}
//int main() {
//	graph_create();
//	Dijkstra(0);
//	return 0;
//}






//#include <iostream>
//#include <cmath>
//#include <algorithm>
//using namespace std;
//#define Maxsize 100
//typedef struct {
//	int u; // 起点 
//	int v; // 终点 
//	int w; // 权值 
//}Edge;
//bool cmp(Edge x, Edge y)//排序基准
//{
//	return x.w < y.w;
//}
//int Kruskal(int a[], int b[], int n)
//{
//	Edge E[Maxsize];
//	int V[Maxsize];
//	int i, j, k = 0, num = 1, sum = 0;
//	for (i = 1; i < n; i++)
//		for (j = 0; j < i; j++)
//		{
//			E[k].u = i;
//			E[k].v = j;
//			E[k].w = abs(a[i] - a[j]) + abs(b[i] - b[j]);
//			k++;
//		}
//	for (i = 0; i < n; i++)
//		V[i] = i;
//	sort(E, E + k, cmp);
//	for (i = 0; num < n; i++)
//	{
//		int start = E[i].u;
//		int end = E[i].v;
//		int v1 = V[start], v2 = V[end]; // 获取两点的集合号 
//		if (v1 != v2)//不在同一个集合里面
//		{
//			sum += E[i].w;
//			num++;
//			for (j = 0; j < n; j++)
//				if (V[j] == v2)
//					V[j] = v1;
//		}
//	}
//	return sum;
//}
//int main(void)
//{
//	cout << endl << "样例" << endl;
//	int n1 = 5;
//	int a1[5] = { 3,7,4,1,8 };
//	int b1[5] = { 6,9,4,7,2 };
//	cout << Kruskal(a1, b1, n1) << endl;
//
//	cout << endl << "测数数据： 1" << endl;
//	int n2 = 5;
//	int a2[5] = { 6,7,7,3,1 };
//	int b2[5] = { 2,7,9,3,4 };
//	cout << Kruskal(a2, b2, n2) << endl;
//
//	cout << endl << "测数数据： 2" << endl;
//	int n3 = 4;
//	int a3[4] = { 7,5,2,9 };
//	int b3[4] = { 2,6,1,5 };
//	cout << Kruskal(a3, b3, n3) << endl;
//
//	cout << endl << "测数数据： 3" << endl;
//	int n4 = 7;
//	int a4[7] = { 34,90,66,73,10,54,97 };
//	int b4[7] = { 89,44,27,75,2,1,89 };
//	cout << Kruskal(a4, b4, n4) << endl;
//
//	cout << endl << "测数数据： 4" << endl;
//	int n5 = 10;
//	int a5[10] = { 33,32,20,55,64,19,59,47,98,54 };
//	int b5[10] = { 16,89,80,85,29,89,49,43,51,47 };
//	cout << Kruskal(a5, b5, n5) << endl;
//
//	cout << endl << "测数数据： 5" << endl;
//	int n6 = 20;
//	int a6[20] = { 3462,1422,342,2777,3247,9225,5092,8520,5458,7998,8887,5489,2559,216,9395,4955,5761,6992,7419,3950 };
//	int b6[20] = { 2927,1642,86,770,883,5982,82,8848,1258,2369,6057,8982,2715,7846,3165,1528,462,6559,2429,8707 };
//	cout << Kruskal(a6, b6, n6) << endl;
//
//	return 0;
//}



//#include <iostream>
//#include <algorithm>
//#include <string>
//#include <stack>
//
//const int MAXN = 100;
//const int MAXM = 200;
//
//using namespace std;
////路径
//struct node {
//	int u, v, w;
//}edge[MAXN] = {
//				{0, 1, 6}, {0, 2, 4}, {0, 3, 5},
//				{1, 4, 1}, {2, 4, 1}, {3, 7, 2},
//				{4, 5, 9}, {4, 6, 7}, {7, 8, 4},
//				{5, 8, 2}, {6, 8, 4} };
//
//int n = 9, m = 11;
//int MAT[MAXN][MAXN];	//表
//int cnt[MAXN];			//入度
//int TS[MAXN], idx;		//拓扑序列
//int ve[MAXN], vl[MAXN];	//最早完工时间
//int e[MAXM], l[MAXM], d[MAXM];	//最早发生时间 最晚发生时间 时间余量
//int keyact[MAXN];		//关键活动
//
//void mat() {	//初始化表
//	int u, v, w;
//	for (int i = 0; i < n; ++i)
//		MAT[i][i] = 0;
//
//	for (int i = 0; i < m; ++i) {
//		u = edge[i].u, v = edge[i].v, w = edge[i].w;
//		MAT[u][v] = w;
//	}
//}
//
//void disp_mat() {	//输出表
//	for (int i = 0; i < n; ++i) {
//		printf("|");
//		for (int j = 0; j < n; ++j) {
//			if (MAT[i][j] == -1) printf(" - ");
//			else printf(" %d ", MAT[i][j]);
//		}
//		puts("|");
//	}
//}
//
//void top() {	//拓扑排序
//	for (int i = 0; i < n; ++i)
//		for (int j = 0; j < n; ++j)
//			if (MAT[j][i] > 0) cnt[i]++;
//	stack <int> st;		//定义栈
//	for (int i = 0; i < n; ++i)
//		if (cnt[i] == 0) st.push(i);	//入度为0进栈
//	while (!st.empty()) {
//		int k = st.top();
//		st.pop();
//		TS[idx++] = k;
//		for (int i = n - 1; i >= 0; --i) {
//			if (MAT[k][i] > 0) {
//				cnt[i]--;
//				if (cnt[i] == 0)
//					st.push(i);
//			}
//		}
//	}
//	for (int i = 0; i < n; ++i)	//输出拓扑序列
//		printf("%c ", TS[i] + 65);
//	puts("");
//}
//
//void getv() {		//计算ve和vl
//	for (int i = 0; i < n; ++i) {
//		int k = TS[i];
//		ve[k] = 0;
//		for (int j = 0; j < n; ++j) {
//			if (MAT[j][k] > 0) {
//				ve[k] = max(ve[k], ve[j] + MAT[j][k]);
//			}
//		}
//	}
//	vl[n - 1] = ve[n - 1];
//	for (int i = n - 2; i >= 0; --i) {
//		int k = TS[i];
//		vl[k] = 32767;
//		for (int j = 0; j < n; ++j) {
//			if (MAT[k][j] > 0)
//				vl[k] = min(vl[k], vl[j] - MAT[k][j]);
//		}
//	}
//	for (int i = 0; i < n; ++i) {
//		printf("ve[%c] = %d\tvl[%c] = %d\n", i + 65, ve[i], i + 65, vl[i]);
//	}
//	puts("");
//}
//void act() {		//计算活动发生时间
//	for (int i = 0; i < m; ++i) {
//		e[i] = ve[edge[i].u];
//		l[i] = vl[edge[i].v] - edge[i].w;
//		d[i] = l[i] - e[i];
//		printf("e[a%d] = %d\tl[a%d] = %d\td[a%d] = %d\n", i + 1, e[i], i + 1, l[i], i + 1, d[i]);
//	}
//	puts("");
//}
//
//void key() {		//查找关键路径
//	int k = 0;
//	printf("key activity : ");
//	for (int i = 0; i < m; ++i) {
//		if (d[i] == 0) {
//			keyact[i] = 1;
//			printf("a%d ", i + 1);
//		}
//	}
//	puts("");
//	int begin = TS[0];
//	printf("key road :%c", begin + 65);
//	while (begin != TS[n - 1]) {
//		for (int i = 0; i < m; ++i) {
//			if (keyact[i] && edge[i].u == begin) {
//				printf("->%c", edge[i].v + 65);
//				begin = edge[i].v;
//			}
//		}
//	}
//}
//int main()
//{
//	memset(MAT, -1, sizeof MAT);
//	mat();
//	disp_mat();
//	top();
//	getv();
//	act();
//	key();
//	return 0;
//}





//#include<iostream>
////#include<stdio.h>
//using namespace std;
//typedef char VerTexType;
//typedef int ArcType;
//#define MaxInt 32767 
//#define MVNum 100    
//#define OK 1
//#define ERROR -1;
//typedef int status;
//
//typedef struct t{
//	VerTexType vexs[MVNum]{ 'A','B','C','D','E','F' };
//	ArcType arcs[MVNum][MVNum];
//	int vexnum = 6, arcnum = 10;
//}AMGraph;
//
//typedef struct {
//	VerTexType adjvex;//最小边在顶点集U的顶点 
//	ArcType lowcost;//最小边上的权值 
//}Closedge[MVNum];
////其实说白了就是adjvex就是某条边的起点，lowcost就是权值（距离）,closedge[i]的i是终点。
////理解好这个很重要。 
//status CreateUDN(AMGraph& G) {//创建无向图 	
//	for (int i = 0; i < G.vexnum; i++) {
//		for (int j = 0; j < G.vexnum; j++) {
//			if (i == j) {
//				G.arcs[i][j] = 0;
//			}
//			else
//				G.arcs[i][j] = MaxInt;//初始状态全部节点之间相互不可达
//		}
//	}
//	G.arcs[0][1] = 6; G.arcs[0][2] = 1; G.arcs[0][3] = 5;
//	G.arcs[1][2] = 5; G.arcs[1][4] = 3;
//	G.arcs[2][3] = 5; G.arcs[2][4] = 6; G.arcs[2][5] = 4;
//	G.arcs[3][5] = 2;
//	G.arcs[4][5] = 6;
//	for (int i = 0; i < G.vexnum; i++) {
//		for (int j = 0; j < G.vexnum; j++) {
//			if (G.arcs[i][j] != MaxInt) {
//				G.arcs[j][i] = G.arcs[i][j];
//			}
//		}
//	}//矩阵对称 
//	return OK;
//}
//
//void ShowGraph(AMGraph G) {
//	cout << " ";
//	for (int i = 0; i < G.vexnum; i++) {
//		cout << " " << G.vexs[i];
//	}
//	cout << endl;
//	for (int i = 0; i < G.vexnum; i++) {
//		cout << G.vexs[i] << " ";
//		for (int j = 0; j < G.vexnum; j++) {
//			if (G.arcs[i][j] == MaxInt) {
//				cout << "* ";
//			}
//			else {
//				cout << G.arcs[i][j] << " ";
//			}
//		}
//		cout << endl;
//	}
//}
//
//int LocateVex(AMGraph G, VerTexType v) {
//	int i;
//	for (i = 0; i < G.vexnum; i++) {
//		if (G.vexs[i] == v) {
//			return i;
//		}
//	}
//	return ERROR;
//}
//
//int Min(Closedge close, AMGraph G) {
//	int min = MaxInt;
//	int mini;
//	for (int i = 0; i < G.vexnum; i++) {
//		if (min > close[i].lowcost && close[i].lowcost != 0) {//不等于0是指不和自身比较，没意义 
//			min = close[i].lowcost;
//			mini = i;
//		}
//	}
//	//	cout<<mini<<endl;
//	return mini;
//}
//
//void Prim(AMGraph& G, VerTexType v) {
//	int vi = LocateVex(G, v);//获取起始点的下标
//	Closedge close;//辅助数组，用来记录不同点之间的距离以及起始位置（可理解为是一个点边集合） 
//	for (int i = 0; i < G.vexnum; i++) {
//		if (vi != i) {
//			close[i].adjvex = v;
//			close[i].lowcost = G.arcs[vi][i];//初始化辅助数组close,让起点直连其它节点（就是假设起点到全部点的距离都是最短） 
//		}
//		else {
//			close[i].lowcost = 0;//0表示自身或该边已被选取。 
//		}
//	}
//	for (int i = 1; i < G.vexnum; i++) {//i从1开始是因为循环不需要执行vexnum次，不必管节点到自己的距离 
//		int k = Min(close, G);//获取当前点边集合里边权值最小的终点（close里下标表示终点，adjvex表示起点，lowcost表示权值） 
//		VerTexType start = close[k].adjvex;//当前边集合里最短边的起点
//		VerTexType end = G.vexs[k];//当前边集合里最短边的终点
//		cout << start << "-" << close[k].lowcost << "-" << end << endl;//输出本次找出来的最短边及端点
//		for (int j = 0; j < G.vexnum; j++) {//更新close表 
//			if (G.arcs[k][j] < close[j].lowcost) {//如果end到j点的距离小于start到j点的距离 
//				//这是以对象的形式简写 
//				close[j] = { G.vexs[k],G.arcs[k][j] };//最短距离从start到j点距离修改成end到j点的距离 
//				//等价于这样写
////				close[i].adjvex=G.vexs[k]; 
////				close[i].lowcost=G.arcs[k][j];
//			}//if
//		}//for 
//	}
//}
//
//int main() {
//	AMGraph G;
//	CreateUDN(G);
//	ShowGraph(G);
//	Prim(G, 'A');
//	return 0;
//}
//



#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXVEX 10
typedef char VerType;	//顶点值类型

struct EdgeNode {
	int adjvex;	//邻接点域，存储该顶点对应的下标
	int weight;	//用于存储权值，对于非网图可以不需要
	EdgeNode* next;	//下一个结点 
};

struct VertexNode {
	int in;	//入度
	VerType data;	//值
	EdgeNode* firstedge;	//邻接表头指针 
};

struct Graph {
	VertexNode vers[MAXVEX];
	int numVertexes, numEdges;	//顶点数和边数 
};

/* 拓扑排序，若G没有回路，则输出拓扑排序序列并返回OK，若有回路返回ERROR */
bool TopologicalSort(Graph* G) {
	EdgeNode* e;
	int i, k, gettop;
	int top = 0;	//栈指针下标
	int count = 0;	//统计输出顶点个数
	int* stack;	//存储入度为0的顶点
	stack = (int*)malloc(G->numVertexes * sizeof(int));

	for (i = 0; i < G->numVertexes; i++)	//遍历所有结点 
		if (G->vers[i].in == 0)
			stack[++top] = i;	//将入度为0的顶点入栈

	while (top != 0) {
		gettop = stack[top--];	//出栈
		printf("%c ", G->vers[gettop].data);
		count++;	//统计输出顶点数
		for (e = G->vers[gettop].firstedge; e; e = e->next) {
			//弧表遍历
			k = e->adjvex;
			if (!(--G->vers[k].in))	//将k号顶点邻接点的入度减1
				stack[++top] = k;	//若为0则入栈，以便下次循环输出 
		}
	}
	if (count < G->numVertexes)	//如果count小于顶点数，说明存在环
		return false;
	else
		return true;
}

/* 图初始化 */
void CreateGraph(Graph* G) {
	int i, m, n;

	printf("输入顶点数和边数：\n");
	scanf("%d,%d", &G->numVertexes, &G->numEdges);
	printf("输入顶点值：\n");
	for (i = 0; i < G->numVertexes; i++) {
		getchar();	//吃掉回车
		scanf("%c", &G->vers[i].data);
	}
	//初始化图头结点指针和入度值 
	for (i = 0; i < G->numVertexes; i++) {
		G->vers[i].firstedge = NULL;
		G->vers[i].in = 0;	//入度为0 
	}
	printf("输入边：\n");
	for (i = 0; i < G->numEdges; i++) {
		scanf("%d,%d", &m, &n);
		EdgeNode* newNode = (EdgeNode*)malloc(sizeof(EdgeNode));
		newNode->next = G->vers[m].firstedge == NULL ? NULL : G->vers[m].firstedge;
		newNode->adjvex = n;
		G->vers[m].firstedge = newNode;
		G->vers[n].in++;	//入度+1 
	}
}

int main() {

	Graph* G = (Graph*)malloc(sizeof(Graph));
	CreateGraph(G);
	if (TopologicalSort(G)) {
		printf("拓扑排序完成！\n");
	}
	else {
		printf("图存在环");
	}
	return 0;
}
